package com.example.interview.algorithm;

/**
 * 二分查找
 *
 * @author gaobing
 * @Description: TODO
 * @date 2018年9月28日 下午4:28:52
 * <p>
 * 先决条件：数据元素必须是有序的 二分算法步骤描述 ① 首先确定整个查找区间的中间位置 mid = （ left + right ）/ 2 ②
 * 用待查关键字值与中间位置的关键字值进行比较； 若相等，则查找成功 若大于，则在后（右）半个区域继续进行折半查找
 * 若小于，则在前（左）半个区域继续进行折半查找 二分查找算法讨论： 优点：ASL≤log2n，即每经过一次比较,查找范围就缩小一半。经log2n
 * 次计较就可以完成查找过程。
 * 缺点：因要求有序，所以要求查找数列必须有序，而对所有数据元素按大小排序是非常费时的操作。另外，顺序存储结构的插入、删除操作不便利。
 */
public class Test00erfenchazhao {

    public static void main(String[] args) {
        int srcArray[] = {3, 5, 11, 17, 21, 23, 28, 30, 32, 50, 64, 78, 81, 95, 101};
        System.out.println(binarySearch(srcArray, 0, srcArray.length - 1, 81));
        System.out.println(binarySearch(srcArray, 81));


    }

    /**
     * 二分查找递归实现 https://gitee.com/gaobing/design.git
     *
     * @param arr
     * @param key
     * @return
     */
    private static int binarySearch(int[] arr, int low, int high, int key) {
        if (key < arr[low] || key > arr[high] || low > high) {
            return -1;
        }
        int middle = (low + high) / 2;// 索引
        if (arr[middle] > key) {
            return binarySearch(arr, low, middle - 1, key);
        } else if (arr[middle] < key) {
            return binarySearch(arr, middle + 1, high, key);
        } else {
            return middle;
        }
    }

    /**
     * 二分查找普通循环实现
     *
     * @param arr 有序数组
     * @param key 查找的元素
     * @return key值所在索引的位置
     */
    private static int binarySearch(int[] arr, int key) {

        if (arr == null || arr.length == 0) {
            return -1;
        }
        int low = 0;
        int high = arr.length - 1;
        int middle = 0; // 数组索引

        if (key < arr[low] || key > arr[high]) {
            return -1;
        }
        while (high >= low) {
            middle = (low + high) / 2;
            if (arr[middle] > key) {
                // 在zuo侧
                high = middle - 1;
            } else if (arr[middle] < key) {
                // 在you侧
                low = middle + 1;
            } else {
                return middle;
            }
        }
        return -1;
    }
}
